1. Field of the Invention
The present invention generally relates to an image processing technique. More particularly, the present invention relates to an image filling method, an apparatus and a computer readable medium storing the program.
2. Description of the Related Art
First, the related art which corresponds to the after-mentioned first object will be described. Conventionally, a line drawing on a sheet of paper is transferred to a cell which is colored manually with a paintbrush when producing animation. Recently, this work is being replaced by digital painting in which the line drawing is digitized by a scanner and is filled by using a computer. Therefore, it becomes easy to fill the line drawing which was very difficult conventionally. However, it is necessary to fill the digitized line drawing data manually one by one even after the digital painting is introduced.
As conventional techniques, Japanese patent No.2835752 and Japanese laid open patent application No.9-134422 disclose a technique for filling a plurality of line drawings at a time by specifying coordinates (a seed point) from which the filling is started, wherein the coordinates are common for regions where a plurality of line drawings are superimposed and filled with the same color.
In the technique of the Japanese patent No. 2835752, the barycenter position of each closed region, and lateral and vertical lengths of a circumscribed rectangle of each closed region are extracted from an unfilled image and the filled image as features. Then, the unfilled image is filled by referring to the corresponding region of the filled image by using the features. According to the above invention, a region which has relatively small movement can be filled with the same color of the corresponding region of the filled image.
In the Japanese laid open patent application No.9-134422, when filling closed regions of a line drawing, a point determined in the closed region and a color selected according to the point are correlated and stored. When the point is located in the same closed region of next images that follows, the color corresponding to the point is called and added to the closed region. Accordingly, filling images which moves successively can be performed speedily and effectively.
However, in the invention of the Japanese patent No.2835752, since only the barycenter position of each closed region and lateral and vertical lengths of a circumscribed rectangle of each closed region are extracted, and used as feature data, there is a problem that the calculation amount for obtaining the barycenter position is large.
In the invention of the Japanese laid open patent application No.9-134422, when overlapping closed regions of a plurality of unfilled line images should be filled with the same color, the closed regions can be filled in a stroke with a seed point which has the same coordinates in the plurality of line drawings. Thus, the invention is built on a premise that there are overlapping closed regions which have the same meaning and should be filled with the same color in a plurality of line drawings. Therefore, this method can be applied to only regions with relatively small movement, thereby there is a problem that many judgments by the operator are necessary.
Next, the related art which corresponds to the second object will be described. Conventionally, a boundary line of red, blue or the like (a colored line) is used as well as a black boundary line when producing animation. There is a following rule.
When a line drawing on a sheet of paper is transferred to a cell, only the black boundary lines are transferred. Then, if a red boundary line is specified when the transferred cell is put on the line drawing, the red boundary line is traced by the brighter color which is one of colors of sides which are divided by the boundary line. If a blue boundary line is specified when the transferred cell is put on the line drawing, the blue boundary line is traced by the darker color which is one of colors of each side which is divided by the boundary line.
In recent years, the line drawings are digitized and digital painting becomes widespread, in which the line drawing is transferred to the cell and is filled on a computer. Thus, the color of the colored line (boundary line) of red or blue should be changed sooner or later on a computer. FIG. 1A shows the line drawing drawn by the colored line and FIG. 1B shows the filled image of the line drawing. The colored line in the filled image needs to be filled with a proper color as shown in FIG. 1C. For this purpose, there are conventional technologies such as a paint bucket tool, a filling process method with function of filling the colored line and the Japanese patent No.2762753.
The paint bucket tool is a common name of a filling tool widely used for a general painting system and the like. When a pixel is specified by a pointing device such as a mouse, pixels which are connected to the pointed pixel and have the same color as the color of the pointed pixel are filled with a predetermined color by the paint bucket tool. FIGS. 2A-2D show a general example for filling a colored line by using the paint bucket tool. When filling a closed region enclosed by a colored line and the colored line shown in FIG. 2A by using the paint bucket tool, the closed region is filled by the paint bucket tool first (FIG. 2B), then the colored line is filled with the same color (FIG. 2C). As a result, the image shown in FIG. 2D is obtained. The order in which the processing shown in FIG. 2B and the FIG. 2C can be reverse.
On the other hand, the filling process method with function of filling the colored line is adopted by software specialized for animation filling. According to the method, the colored line is filled with the color used for filling the region enclosed by the colored line at the same time when the region is filled. FIGS. 3A, 3B shows the example. As shown FIGS. 3A, 3B, the closed region enclosed by the colored line and the colored line are filled at the same time when the inside of the closed region is filled. As a consequence, the colored line is filled with the color which is used first for filling each region enclosed by the colored line.
In the method of the Japanese patent No.2762753, every closed region is labeled and a filter of a size is defined, in which the filter is centered by a target pixel on a boundary line when the boundary line is the colored line. Then, the maximum label number within the filter is provided to the target pixel. The processing will be described with reference to FIGS. 4A-Ac. As shown in FIG. 4A, a label number 5 is assigned to the upper closed region of the colored line and a label number 23 is assigned to the lower closed region. As shown in FIG. 4B, by applying the filter which is wider than the thickness of the colored line, the maximum label number within the filter is assigned to the label number of the colored line. As a result, as shown in FIG. 4C, the label number of the colored line becomes 23.
However, in the case when a colored line should be filled with a plurality of colors, there is a following problem. As shown in FIGS. 5A and 5B, by using the paint bucket tool, the same color pixels which are connected successively to a pixel on which the paint bucket tool is applied are filled with a color. Therefor, for filling such a colored line by using the paint bucket tool, the region on which the paint bucket tool is applied should be specified in advance as shown in FIG. 6A such that the paint bucket tool is applied in the specified region as shown in FIG. 6B. Such a case occurs very frequently in which a colored line should be divided and filled with a plurality of colors. However, there is a problem in that it takes much time to specify the regions to which the paint bucket tool is applied in a shape of the colored line.
FIG. 7 shows the problem of the filling tool with filling function to the colored line. The filling tool has a rule in which the colored line is filled with a color of the closed region which is filled first. Therefore, as shown in FIG. 7, the colored line is filled differently depending on the side which is filled first. That is, when the inside is filled first, the colored line is filled with red. When the outside is filled first, the colored line is filled with blue. Thus, the operator should be aware of the color of the colored line and the colors of the closed regions which are divided by the colored line. That is, when the colored line is red, the closed region which is brighter side of the closed regions which are divided by the colored line should be filled first. When the colored line is blue, the closed region which is darker side of the closed regions which are divided by the colored line should be filled first. There is a problem that the operator should always pay particular attention to the color of the colored line and the order of filling. In addition, the same problem which is explained in FIG. 5 exists in the filling tool with function of filling the colored line as shown in FIGS. 8A and 8B. For avoiding the problem, it is necessary to perform the same tasks shown in FIG. 6 by the filling tool with function of filling the colored line as shown in FIGS. 9A and 9B. Therefore, it takes much time to set regions for applying.
According to the method shown in the Japanese patent No.2762753, the label number of the colored line is determined as one of label numbers of closed regions. Thus, the color of the colored line is not determined until the filling process is performed as shown in FIG. 10A. Therefore, there is a problem that the above-mentioned rule which has been historically established in producing animation can not be considered. In addition, when the size of the filter is too small (FIGS. 10B and 10C) or too large (FIG. 10D), the processing is not performed properly. Thus, it is necessary to adjust the size of the filter according to the thickness or the complexity of the colored lines. However, the Japanese patent No.2762753 does not disclose the method for solving the problem.
Next, the related art corresponding to the third object will be described.
For filling a closed region in a line drawing to be filled, at least coordinates in the closed region and the color to be pained are required. The coordinates can be specified by a pointing device such as a mouse when a computer is used for filling. As for the color, an operator inputs (R, G, B) values or (tint, chroma, lightness) values and the like by using an interface shown in FIGS. 11A and 11B.
There is another method in which a color is obtained by specifying a point by the pointing device on a display such that the color is used for painting. FIGS. 12A and 12B show two representative examples. In the method shown in FIG. 12A, a color specifying table is displayed in which predetermined colors and the corresponding names are shown. The operator specifies a desired color in the table with the pointing device. In the case shown in FIG. 12B, an example image which is already filled is displayed. In this case, the operator finds a closed region in the example image which has a color the operator wants to use and specifies the color with the pointing device.
However, since the color value used for painting each closed region is strictly defined in producing animation, the operator needs to check the color value and input it via a keyboard every time the color is changed by the method shown in FIGS. 11A and 11B. Thus, this operation is burdensome to the operator.
As for the method shown in FIGS. 12A and 12B, there is a problem that the operator needs to move the pointing device extensively every time the color to be painted is changed.
Next, the related art corresponding to the fourth object will be described.
Conventionally, for filling a region enclosed by a line, the operator specifies the color and coordinates (which will be called a seed point) which is a start point for filling. Then, the four connected pixel seed fill algorithm, the eight connected pixel seed fill algorithm or the scan line seed fill algorithm is generally used for painting the region. These methods are explained, for example, in xe2x80x9cHands-on Computer Graphicsxe2x80x9d, Fujio Yamaguchi, Nikkan Kogyo shinbun-sha, pp104-, 1987. Each methods will be described in the following.
FIG. 13 is a diagram for explaining the four connected pixel seed fill algorithm. First, the color of the specified seed point is checked. When the color can be changed (that is, when the color is not the color of the outline, for example), the color value of the pixel is saved and the color of the seed point is changed to a specified color. Next, pixels which are connected to each of four sides of the seed point are searched. If the color of the searched pixel can be changed (that is, when the color is the same as the saved color and is not the color of the outline), the color of the pixel is changed to the specified color. Next, the same processing is performed for four pixels which are connected to the pixel in which the color is changed. After that, the same processing is performed recursively until a pixel which has a color different from the saved color or a pixel which has the color same as the outline color is searched. FIG. 13 shows pixels 1-4 which are filled in the first filling process and pixels adjacent to the pixel 1 which are further searched and filled.
FIG. 14 is a diagram for explaining the eight connected pixel seed fill algorithm. In the algorithm, as shown in FIG. 14, this method is different from the four connected pixel seed fill algorithm in that eight connected pixels are searched in this method. FIG. 14 shows pixels 1-8 which are filled in the first filling process and pixels around the pixel 3 which are further searched and painted.
According to the above-mentioned algorithm, the recursive processing tends to become deep and large stack region is necessary. FIG. 15 is a diagram for explaining the scan line seed fill algorithm which is developed for the sake of decreasing the depth of the recursive processing.
First, the color of the seed point which is specified in the first place is checked. When the color can be changed (for example, when the color is not the color of the outline), the color value of the pixel is saved and the color is changed to a specified color. Next, pixels are searched from the seed point in the lateral direction until a pixel in which the color can not be changed is searched (for example, the color of the pixel is different from the saved color or the color of the pixel is that of the outline). When a pixel in which the color can be changed is searched (for example, the color of the pixel is the same as the saved color or the color of the pixel is not that of the outline), the color is changed. In addition, the color of a pixel which is connected to the upper side or the lower side of the searched pixel is checked while searching the pixels. Then, the coordinates of the rightmost (or leftmost) pixel in which the color can be changed are stored. The same processing is repeated recursively by using the pixel of the coordinates as a seed point. As a result, the color of the closed region which includes the seed point which is specified in the first place is changed to a specified color.
In the above-mentioned conventional methods, the four connected pixel seed fill algorithm is easily programmable and the processing is fast. In addition, the four connected pixel seed fill algorithm does not have the after-mentioned problem of the eight connected pixel seed fill algorithm. Therefore, this algorithm is widely used.
However, when a region is painted once by specifying a seed point as shown in FIG. 16A, unfilled regions remain as shown in FIG. 16B due to the basic characteristics of this algorithm. Such a case often occurs when producing animation such as shown in FIG. 17. In many cases, the remaining region is a small region such as one pixel or two pixels. Thus, the remaining region is often undetected by the naked eye. Therefore, the operator must concentrate on checking the minute remaining region, which takes much time.
As for the eight connected pixel seed fill algorithm, the problem of unpainted region remaining does not occur. However, in the case such as one shown in FIG. 18, the color used for painting the inside leaks at the point specified the arrow in FIG. 18 such that the outside is painted by the same color. The case shown in FIG. 18 also often occurs. Therefore, this method is not generally used.
The scan line seed fill algorithm has the same merits and demerits as the four connected pixel seed fill algorithm in terms of painting. As mentioned above, this method require smaller stack region that the other two methods. However, the relatively large stack region used for the other two methods is much smaller that the program region or the data region. Thus, there is no reason to use the scan line seed fill algorithm instead of the four connected pixel seed fill algorithm which is easily implemented at the present time when the price of a computer memory is very low.
Since the remaining region to be checked is minute in any of the above-mentioned algorithms, it is difficult to detect the remaining region. Thus, the operator should intensively concentrate on checking whether-the unfilled region is remained, however, it takes much time.
It is a first object of the present invention to provide an image filling method, apparatus, and a computer readable medium storing an image filling program in which computational amount can be decreased when determining a color used for filling a closed region of a line drawing with reference to a reference line drawing, and it is not necessary for the user to check overlapping state of line drawings.
It is a second object of the present invention to provide an effective and flexible image filling method, apparatus, and a computer readable medium storing an image filling program in which, even when a colored line extends over a plurality of regions, the user can change the color of only a necessary part of the colored line without affecting other regions such that it is not necessary for the user to consider the filling order.
It is a third object of the present invention for the user to save labor when filling images.
It is a fourth object of the present invention for the user to check and correct easily an unfilled small region (one pixel, two pixels or the like) which is forgotten or is a mistake when filling a digitized line drawing which is used in producing animation, in which high concentration is not necessary for the user to check the small region.
According to a first aspect of the present invention, the above object of the present invention is achieved by an image filling method comprising the steps of:
separating a reference line drawing into first closed regions, the reference line drawing being read from a storage device and being an original line drawing of a reference picture;
extracting at least one feature amount of the first closed regions other than the barycenter;
separating a line drawing to be filled into second closed regions, the line drawing to be filled being read from a storage device;
extracting at least one feature amount of the second closed regions other than the barycenter;
calculating variations of feature amounts between every combination of the first closed regions and the second closed regions, sorting the first closed regions in ascending order by the variation of the feature amount for each of the second closed regions;
generating color candidate lists for each of the second closed regions, wherein color information corresponding to the first closed regions is obtained from the reference picture and duplication of the color information is eliminated;
filling each of the second closed regions with a color which is on the top of the color candidate list corresponding to the second closed region.
According to the above-mentioned invention, the barycenter is not used for the feature amount because calculation amount is very large for obtaining the barycenter of a shape.
According to the present invention, the following feature amounts are used.
a) Central coordinates of a minimum rectangular circumscribing a closed region.
b) The area of the minimum rectangular circumscribing the closed region.
c) The aspect ratio of the minimum rectangular circumscribing the closed region.
d) The number of pixels constituting the closed region.
e) The ratio between b and d.
f) The peripheral length of the closed region.
g) The ratio between f and the square root of d.
According to the present invention, similar shapes can be found accurately by using the above feature amounts instead of calculating the barycenter.
In addition, the line drawing can be automatically filled with the top color in the color candidate list.
Further, according to the above-mentioned invention, the seed point can be placed at any point in a closed region since closed regions between the reference picture and the line drawing to be filled are related by the shape and the location, not by the seed point. Thus, the seed point can be set properly by a program. Therefore, the filling process can be performed automatically without the user""s judgment and the like, in which the user does not need to check overlapping state between the line drawings. Even when a filling error occurs, the user can change the erroneous color by displaying the color candidate list at any point in a closed region. Thus, the user does not need to be conscious of the seed point.
The above-mentioned image filling method may further includes the steps of:
presenting the filled line drawing to a user;
presenting the color candidate list corresponding to each closed region of the filled line drawing according to a request by the user;
changing a color of a closed region which is specified by the user into a color which is selected by the user from the color candidate list.
Accordingly, it becomes easy for the user to check and correct an erroneous color of the closed region with a minimum movement of a mouse pointer. In addition, the filled line drawing which is checked and corrected by the user may be used as the next reference picture, and the original line drawing may be used as the reference line drawing such that remained unfilled line drawings are automatically filled again according to an instruction. Further, filling errors can be decreased after this.
Further, the image filling method may include the steps of:
generating a color alias list which has aliases corresponding to color information, and storing the color alias list in a storage device;
reading the color alias list from the storage device; and
providing color aliases to the color candidate list to be displayed.
Accordingly, the user can select a color easily and accurately.
According to a second aspect of the present invention, the above object of the present invention is achieved by an image filling method comprising the steps of:
extracting color information of each pixel of a line drawing to be filled, wherein the line drawing to be filled includes a colored line which is a boundary line dividing the line drawing to be filled into regions, a color of the boundary line specifying a color used for filling the boundary line;
extracting boundary line information representing whether the each pixel is on the boundary line or not by using the color information;
filling the line drawing except the boundary line by using the boundary line information; and
filling the colored line by using the boundary line information.
According to the above-mentioned invention, a region can be filled without affecting any boundary line. In addition, a colored line can be filled without affecting any other region. Thus, the user can perform filling effectively and flexibly according to the conventional rule in producing animation.
According to a third aspect of the present invention, the above object of the present invention is achieved by an image filling method comprising the steps of:
generating color specifying information including predetermined colors and corresponding names;
displaying the color specifying information at coordinates when a user specifies a closed region by pointing the coordinates with a pointing device; and
filling the closed region with a color specified by the user from the displayed color specifying information.
According to the third aspect of the present invention, the above object of the present invention is also achieved by an image filling apparatus comprising:
a part for generating color specifying information including predetermined colors and corresponding names according to an instruction by a user;
a storage device;
a part for storing generated color specifying information in the storage device;
a part for reading a line drawing to be filled from the storage device;
a part for displaying the line drawing to be filled on a display;
a part for reading the color specifying information from the storage device;
a part for displaying the color specifying information at coordinates specified by a pointing device on the display by the user;
a part for filling a closed region which includes the coordinates with a color specified by the pointing device from the color specifying information; and
a part for storing the line drawing which is filled in the storage device.
According to a fourth aspect of the present invention, the above object of the present invention is achieved by an image processing method comprising the steps of:
inputting image data;
searching the image data for extracting a small region smaller than or equal to a predetermined size; and
outputting a list of the small regions.
The above-mentioned image processing method may include the steps of:
providing a mark to an extracted small region by using a small region list (small region table); and
displaying the mark wherein the mark is overlaid on the image data so as to alert the user to an unfilled small region, a color which is not changed or the like.
Further, the above-mentioned image processing method may include the steps of:
providing a mark to the small region;
displaying the mark wherein the mark is overlaid on the image data; and
asking the user about processing for the small region such that processing specified by the user is performed in an interactive manner.